package com.langsin.Tree;

import com.sun.corba.se.impl.resolver.SplitLocalResolverImpl;

/**
@Auther: MFM
@Date: 2021/8/9 - 08 - 09 - 15:53 
@version: 1.0
*/

public class BinarySearchTree<E extends Comparable<E>> {

    private class Node{
        public E e;
        public Node left;
        public Node right;

        public Node(E e){
            this.e=e;
            this.left=null;
            this.right=null;
        }
    }
    public Node root;
    private int size;

    public BinarySearchTree() {
        root = null;
        size = 0;
    }

    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    public void add(E e){
        root = add(root,e);
    }

    private Node add(Node node,E e){
        //递归的终止条件
        if (node==null){
            size++;
           return new Node(e);
        }

        //递归
        if (e.compareTo(node.e)<0){
           node.left = add(node.left,e);
        }else if (e.compareTo(node.e)>0){
            node.right = add(node.right,e);
        }

        return node;
    }

    //前序遍历
    public void preOrder(){
        preOrder(root);
    }

    public void preOrder(Node node){
        //终止条件
        if (node == null){
            return;
        }

        //递归
        System.out.println(node.e);
        preOrder(node.left);
        preOrder(node.right);
    }

    //中序遍历
    public void inOrder(){
        inOrder(root);
    }

    private void inOrder(Node node){
        //终止条件
        if (node == null){
            return;
        }

        //递归
        inOrder(node.left);
        System.out.println(node.e);
        inOrder(node.right);
    }

    //后序遍历
    public void postOrder(){
        postOrder(root);
    }

    private void postOrder(Node node){
        //终止条件
        if (node == null){
            return;
        }

        //递归
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.e);
    }


}
